package com.stefan.recursion;

//斐波那契数列
public class Demo {

    private int[] memory = null;

    public Demo (int size) {
        memory = new int[size];
    }
    //1123581321
    /*
    * f(n) = f(n-2)+f(n-1)
    * n<=2
    * */
    //without memory
    public int fab(int n) {
        if (n <=2) {
            return 1;
        }
        return fab(n-1) + fab(n-2);
    }

    //with memory
    public int fab1(int n) {
        if (n <=2) {
            return 1;
        }
        if (memory[n]>0) {
            return memory[n];
        }
        int count = fab1(n-1) + fab1(n-2);
        memory[n] = count;
        return count;
    }
    //尾递归 - 传计算好的值
    public int fab2(int n, int v1,int v2) {
        if (n <=2) {
            return v2; //这里不能返回1，这里需要返回最终算好的值
        }
        return fab2(n-1,v2,v1+v2);
    }

    public int noFab (int n) {
        if (n <=2) {
            return 1;
        }
        int f3 = 0 ;
        int f2 = 1;
        int f1 = 1;
        for (int i = 3; i <=n ; i++) {
            f3 = f2+f1;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    public static void main(String[] args) {
        Demo demo = new Demo(46);
//        for (int i = 1; i <= 45; i++) {
//            long start = System.currentTimeMillis();
//            System.out.println(i+": " + demo.fab(i) + " 所花费的时间 : "+(System.currentTimeMillis()-start) + " ms");
//        }
//        System.out.println("===================================");
        for (int i = 1; i <= 45; i++) {
            long start = System.currentTimeMillis();
            System.out.println(i+": " + demo.noFab(i) + " 所花费的时间 : "+(System.currentTimeMillis()-start) + " ms");
        }
        System.out.println("===================================");
        for (int i = 1; i <= 45; i++) {
            long start = System.currentTimeMillis();
            System.out.println(i+": " + demo.fab1(i) + " 所花费的时间 : "+(System.currentTimeMillis()-start) + " ms");
        }
        System.out.println("===================================");
        for (int i = 1; i <= 45; i++) {
            long start = System.currentTimeMillis();
            System.out.println(i+": " + demo.fab2(i,1,1) + " 所花费的时间 : "+(System.currentTimeMillis()-start) + " ms");
        }
    }
}
